package com.github.yangyishe.p100;

import com.github.yangyishe.ListNode;

/**
 * 92. 反转链表 II
 * https://leetcode.cn/problems/reverse-linked-list-ii/?envType=study-plan-v2&envId=top-interview-150
 *
 * 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
 *
 *
 * 示例 1：
 *
 *
 * 输入：head = [1,2,3,4,5], left = 2, right = 4
 * 输出：[1,4,3,2,5]
 * 示例 2：
 *
 * 输入：head = [5], left = 1, right = 1
 * 输出：[5]
 *
 *
 * 提示：
 *
 * 链表中节点数目为 n
 * 1 <= n <= 500
 * -500 <= Node.val <= 500
 * 1 <= left <= right <= n
 *
 *
 * 进阶： 你可以使用一趟扫描完成反转吗？
 */
public class Problem92 {
    public static void main(String[] args) {
        int[] head=new int[]{3,5};
        int left=1;
        int right=2;

        Problem92 problem92 = new Problem92();
        ListNode result = problem92.reverseBetween(ListNode.getInstance(head), left, right);
        result.print();
    }

    /**
     * 思路:
     * 遍历时, 遇到节点顺序在要求范围内时, 创建一个临时节点群, 并逆序将范围内的节点存到节点群.
     * 当马上离开节点范围时, 此时可以获取逆序后的开始节点和结束节点
     * 将逆序后的开始节点设置在原范围节点之左的节点后, 结束节点设置在原范围节点之右的节点前
     *
     * 注意: 边界值情况. 包括左边界和右边界.
     *
     * @param head
     * @param left
     * @param right
     * @return
     */
    public ListNode reverseBetween(ListNode head, int left, int right) {
        int index=0;

        ListNode temp=head;
        ListNode leftOutNode=null;
        ListNode newHeadNode=null;
        ListNode newEndNode=null;
        while(temp!=null){
            index++;
            if(index==left-1){
                leftOutNode=temp;
            }
            if(index>=left&&index<=right){
                newHeadNode=new ListNode(temp.val,newHeadNode);
                if(newEndNode==null){
                    newEndNode=newHeadNode;
                }
            }
            if(index==right+1){
                newEndNode.next=temp;
                break;
//                if(leftOutNode!=null){
//                    leftOutNode.next=newHeadNode;
//                    newEndNode.next=temp;
//                    break;
//                }else{
//                    newEndNode.next=temp;
//                    return newEndNode;
//                }

            }

            temp=temp.next;
        }
        if(leftOutNode!=null){
            leftOutNode.next=newHeadNode;
        }else{
            return newHeadNode;
        }

        return head;
    }
}
